package com.chilly.stack;

/**
 * 42. 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * Created by Chilly Cui on 2020/11/25.
 */
public class TrappingRainWater {
    public static void main(String[] args) {
//        int[] height = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
//        int res = new Solution().trap(height);
//        System.out.println(res); //6

        int[] height2 = new int[]{4, 2, 0, 3, 2, 5};
        int res2 = new Solution().trap(height2);
        System.out.println(res2); //9
    }

    static class Solution {
        /*
        //韦恩图
        public int trap(int[] height) {
            int n = height.length;
            //同时从左往右和从右往左计算有效面积(不管是雨水还是柱子)
            int s1 = 0;
            int s2 = 0;
            int max1 = 0;
            int max2 = 0;
            for (int i = 0; i < n; i++) {
                if (height[i] > max1) {
                    max1 = height[i];
                }
                if (height[n - i - 1] > max2) {
                    max2 = height[n - i - 1];
                }
                s1 += max1;
                s2 += max2;
            }
            //S1 + S2会覆盖整个矩形，并且：重复面积 = 柱子面积 + 积水面积
            //积水面积 = S1 + S2 - 矩形面积 - 柱子面积
            int res = s1 + s2 - max1 * n - sum(height);
            return res;

        }

        private int sum(int[] height) {
            int sum = 0;
            for (int i = 0; i < height.length; i++) {
                sum += height[i];
            }
            return sum;
        }*/

        /*//单调栈O(n)解决
        public int trap(int[] height) {
        }*/

        public int trap(int[] height) {
            int result = 0;
            int maxValue = -1;
            int maxAddr = 0;

            //取数组最大值及其下标
            for (int i = 0; i < height.length; i++) {
                if (height[i] > maxValue) {
                    maxValue = height[i];
                    maxAddr = i;
                }
            }

            //最大值的左半部分处理
            for (int left = 0; left < maxAddr; left++) {
                for (int i = left + 1; i <= maxAddr; i++) {
                    if (height[i] < height[left]) {
                        result = result + (height[left] - height[i]);
                    } else {
                        left = i;
                    }
                }
            }

            //最大值的右半部分处理
            for (int right = height.length - 1; right > maxAddr; right--) {
                for (int i = right - 1; i >= maxAddr; i--) {
                    if (height[i] < height[right]) {
                        result = result + (height[right] - height[i]);
                    } else {
                        right = i;
                    }
                }
            }

            return result;
        }
    }

}
